package com.xcc.dataStructures.demo14_algapplication;

import java.util.*;

/**
 * 贪心算法
 */
public class Demo05_GreedyAlgorithm {

    public static void main(String[] args) {
        Map<String, Set<String>> map = new HashMap<>();
        Set<String> set1 = new HashSet<>();
        set1.add("北京");
        set1.add("上海");
        set1.add("天津");

        Set<String> set2 = new HashSet<>();
        set2.add("广州");
        set2.add("北京");
        set2.add("深圳");

        Set<String> set3 = new HashSet<>();
        set3.add("成都");
        set3.add("上海");
        set3.add("杭州");

        Set<String> set4 = new HashSet<>();
        set4.add("上海");
        set4.add("天津");

        Set<String> set5 = new HashSet<>();
        set5.add("杭州");
        set5.add("大连");

        map.put("K1", set1);
        map.put("K2", set2);
        map.put("K3", set3);
        map.put("K4", set4);
        map.put("K5", set5);

        Set<String> allAreas = new HashSet<>();
        allAreas.addAll(set1);
        allAreas.addAll(set2);
        allAreas.addAll(set3);
        allAreas.addAll(set4);
        allAreas.addAll(set5);

        //存储选择的key
        List<String> selects = new ArrayList<>();

        //定义此时最大的key
        String maxKey;
        //临时存储的set集合
        Set<String> tempSet = new HashSet<>();
        //如果allArea不为空则一直删除
        while (allAreas.size() != 0) {
            //清空临时set
            tempSet.clear();
//            maxSize = 0;
            maxKey = null;
            for (Map.Entry<String, Set<String>> entry : map.entrySet()) {
                tempSet = entry.getValue();
                tempSet.retainAll(allAreas);
                if (tempSet.size() > 0 && (maxKey == null || tempSet.size() > map.get(maxKey).size())) {
                    maxKey = entry.getKey();
                }
            }
            if (maxKey != null) {
                tempSet = map.get(maxKey);
                selects.add(maxKey);
                allAreas.removeAll(tempSet);
                //此时可以将对应的key去除，这样能在遍历map的时候提高效率
                map.remove(maxKey);
            }
        }

        System.out.println(selects);
    }
}
